package 分类.DFS;

public class 岛屿问题 {
    //1.求岛屿数量
    public static int numIslands(char[][] grid){
        int  m=grid.length;
        int n=grid[0].length;
        int res=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1') res++;
                dfs(i,j,grid);
            }
        }
        return res;
    }
    static void dfs(int i,int j,char[][] grid ){
        if(i<0||j<0||i==grid.length||j==grid[0].length) return;
        if(grid[i][j]=='0') return;
        if(grid[i][j]=='1') grid[i][j]='0';
        dfs(i+1,j,grid);
        dfs(i,j+1,grid);
        dfs(i-1,j,grid);
        dfs(i,j-1,grid);
    }


    //2.求封闭岛屿数量，直接减去边上的岛屿就行
    public int closedIsland(char[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int res=0;
        /******************************************/
        for (int i=0;i<n;i++){
            //把靠上边的岛屿淹没
            dfs(0,i,grid);
            //把靠下边的岛屿淹没
            dfs(m-1,i,grid);
        }
        for (int i=0;i<m;i++){
            //把靠左边的岛屿淹没
            dfs(i,0,grid);
            //把靠右边的岛屿淹没
            dfs(i,n-1,grid);
        }
        /********************************************/
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1') res++;
                dfs(i,j,grid);
            }
        }
        return res;
    }


    //3.被围绕的区域
    public void solve(char[][] grid) {
        int m=grid.length;
        if(m==0) return;
        int n=grid[0].length;
        int res=0;
        /******************************************/
        for (int i=0;i<n;i++){
            //把靠上边的岛屿淹没
            dfs1(0,i,grid);
            //把靠下边的岛屿淹没
            dfs1(m-1,i,grid);
        }
        for (int i=1;i<m-1;i++){
            //把靠左边的岛屿淹没
            dfs1(i,0,grid);
            //把靠右边的岛屿淹没
            dfs1(i,n-1,grid);
        }

        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if(grid[i][j]=='A') grid[i][j]='O';
                else if(grid[i][j]=='O') grid[i][j]='X';
            }
        }
    }

    void dfs1(int i,int j,char[][] grid){
        if(i<0||j<0||i==grid.length||j==grid[0].length){
            return;
        }
        if(grid[i][j]=='A'||grid[i][j]=='X') return;
        else if(grid[i][j]=='O') grid[i][j]='A';
        dfs1(i+1,j,grid);
        dfs1(i,j+1,grid);
        dfs1(i-1,j,grid);
        dfs1(i,j-1,grid);
    }


    //4.岛屿的最大面积
    public int maxAreaOfIsland(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int res=0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if(grid[i][j]==1){
                    res=Math.max(res,dfs2(i,j,grid));
                }

            }
        }
        return res;
    }
    int dfs2(int i,int j,int[][] grid){
        if(i<0||j<0||i>=grid.length||j>=grid[0].length) return 0;
        if(grid[i][j]==0) return 0;
        grid[i][j]=0;
        return dfs2(i+1,j,grid)+dfs2(i,j+1,grid)+dfs2(i-1,j,grid)+dfs2(i,j-1,grid)+1;
    }
}
